<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>WEEK 04</title>
</head>

<body>
    <script src="./week04.js"></script>

    <h1>第四周知识点总结</h1>
    <h2>深度优先搜索、广度优先搜索</h2>
    <h3>
        深度优先搜索算法（Depth-First-Search），不撞南墙不回头。以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问。沿着某条路径遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。<br>

        广度优先搜索（Breadth First Search,
        BFS），层层递进。以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。<br>
        迭代实现:<br>
        深度优先搜索，堆栈实现；dfs=栈，压栈，出栈<br>
        广度优先搜索，队列实现；bfs＝队列，入队列，出队列
    </h3>
    <h2>贪心算法</h2>
    <h3>
        Greedy 是一种在每一步选择都
        采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。鼠目寸光，目光短浅。<br>
        贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。<br>
        动态规划则保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。<br>
        贪心：当下做局部最优判断<br>
        回溯：能够回退<br>
        动态规划：最优选择+回退<br><br>
        贪心法可以解决一些最优问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求得答案。<br>
        一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求的的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。<br>
        简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，这种子问题最优解称为最优子结构。（银币问题适合贪心，是因为它本身的面值是倍数，如果不是倍数就不行）<br>
        从后往前看是否可贪心，或从某一局部看
    </h3>
    <h2>二分查找</h2>
    <h3>
        二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
    </h3>
</body>

</html>